/*
 * @lc app=leetcode.cn id=1392 lang=typescript
 *
 * [1392] 最长快乐前缀
 */

// @lc code=start
function longestPrefix(s: string): string {
  const n = s.length;
  const next = new Array(n).fill(-1);
  let j = -1;
  for (let i = 1; i < n; i++) {
    while (j !== -1 && s[i] !== s[j + 1]) {
      j = next[j];
    }
    if (s[i] === s[j + 1]) {
      j++;
    }
    next[i] = j;
  }

  // 返回公共前缀长度
  return s.substring(0, next[n - 1] + 1);
}
// @lc code=end
